Clique-inserted-graphs and spectral dynamics of clique-inserting

Motivated by studying the spectra of truncated polyhedra, we consider the clique-inserted-graphs. For a regular graph G of degree r>0, the graph obtained by replacing every vertex of G with a complete graph of order r is called the clique-inserted-graph of G, denoted as C(G). We obtain a formula for the characteristic polynomial of C(G) in terms of the characteristic polynomial of G. Furthermore, we analyze the spectral dynamics of iterations of clique-inserting on a regular graph G. For any r-regular graph G with r>2, let S(G) denote the union of the eigenvalue sets of all iterated clique-inserted-graphs of G. We discover that the set of limit points of S(G) is a fractal with the maximum r and the minimum −2, and that the fractal is independent of the structure of the concerned regular graph G as long as the degree r of G is fixed. It follows that for any integer r>2 there exist infinitely many connected r-regular graphs (or, non-regular graphs with r as the maximum degree) with arbitrarily many distinct eigenvalues in an arbitrarily small interval around any given point in the fractal. We also present a formula on the number of spanning trees of any kth iterated clique-inserted-graph and other related results.     

From symmetric subdivision masks of Hurwitz type to interpolatory subdivision masks

In this paper we present a general strategy to deduce a family of interpolatory masks from a symmetric Hurwitz non-interpolatory one. This brings back to a polynomial equation involving the symbol of the non-interpolatory scheme we start with. The solution of the polynomial equation here proposed, tailored for symmetric Hurwitz subdivision symbols, leads to an efficient procedure for the computation of the coefficients of the corresponding family of interpolatory masks. Several examples of interpolatory masks associated with classical approximating masks are given.     

On the matching polynomial of subdivision graphs

Let G be a simple graph and let S(G) be the subdivision graph of G, which is obtained from G by replacing each edge of G by a path of length two. In this paper, by the Principle of Inclusion and Exclusion we express the matching polynomial and Hosoya index of S(G) in terms of the matchings of G. Particularly, if G is a regular graph or a semi-regular bipartite graph, then the closed formulae of the matching polynomial and Hosoya index of S(G) are obtained. As an application, we prove a combinatorial identity.     

Nonconvex piecewise linear knapsack problems

This paper considers the minimization version of a class of nonconvex knapsack problems with piecewise linear cost structure. The items to be included in the knapsack have a divisible quantity and a cost function. An item can be included partially in the given quantity range and the cost is a nonconvex piecewise linear function of quantity. Given a demand, the optimization problem is to choose an optimal quantity for each item such that the demand is satisfied and the total cost is minimized. This problem and its close variants are encountered in manufacturing planning, supply chain design, volume discount procurement auctions, and many other contemporary applications. Two separate mixed integer linear programming formulations of this problem are proposed and are compared with existing formulations. Motivated by different scenarios in which the problem is useful, the following algorithms are developed: (1) a fast polynomial time, near-optimal heuristic using convex envelopes; (2) exact pseudo-polynomial time dynamic programming algorithms; (3) a 2-approximation algorithm; and (4) a fully polynomial time approximation scheme. A comprehensive test suite is developed to generate representative problem instances with different characteristics. Extensive computational experiments show that the proposed formulations and algorithms are faster than the existing techniques.     

Chebyshev tau matrix method for Poisson-type equations in irregular domain

In this paper, a new meshless method, Chebyshev tau matrix method (CTMM) is researched. The matrix representations for the differentiation and multiplication of Chebyshev expansions make CTMM easy to implement. Problems with curve boundary can be efficiently treated by CTMM. Poisson-type problems, including standard Poisson problems, Helmholtz problems, problems with variable coefficients and nonlinear problems are computed. Some numerical experiments are implemented to verify the efficiency of CTMM, and numerical results are in good agreement with the analytical one. It appears that CTMM is very effective for Poisson-type problems in irregular domains.     

Constrained inverse min–max spanning tree problems under the weighted Hamming distance

In this paper, we consider the constrained inverse min–max spanning tree problems under the weighted Hamming distance. Three models are studied: the problem under the bottleneck-type weighted Hamming distance and two mixed types of problems. We present their respective combinatorial algorithms that all run in strongly polynomial times. This research is supported by the National Natural Science Foundation of China (Grant No. 10601051).     

Computing matrix functions solving coupled differential models

In this paper a modification of the method proposed in [E. Defez, L. Jódar, Some applications of Hermite matrix polynomials series expansions, Journal of Computational and Applied Mathematics 99 (1998) 105–117] for computing matrix sine and cosine based on Hermite matrix polynomial expansions is presented. An algorithm and illustrative examples demonstrate the performance of the new proposed method.     

矩阵特征多项式的图论计算公式

给出了赋权有向图邻接矩阵特征多项式的图论计算公式,从而得到了一般矩阵特征多项式的图论计算方法,并且研究了赋权有向图邻接矩阵特征多项式和谱半径的一些性质．     

关于勒让德多项式与契贝谢夫多项式间的关系

主要研究勒让德多项式与契贝谢夫多项式之间的关系的性质,利用生成函数和函数级数展开的方法,得出了勒让德多项式与契贝谢夫多项式之间的一个重要关系,这对勒让德多项式与契贝谢夫多项式的研究有一定的推动作用．